Codeforces Round 358 (Div. 2) E. Alyona and Triangles
题意:
$N\le 5000个点,保证任意形成的三角形的面积\le S\le 10^{18}$
$现在构成出一个三角形面积不超过4S,使得包含这个N个点$
分析:
$求个凸包,然后n^2枚举2个点,two pointers旋转卡壳搞出第三个点$
$求出最大三角形,之后把每条边作为对角线搞出大三角形就好了$
$即原来三角形的每个点是新三角形每条边的中点$
$证明方式就反证一下,如果有点在大三角形外$
$那么他作为新的三角形的顶点,拥有更大的高,面积更大,矛盾$
$所以原来的构造方法正确$
$时间复杂度O(n^2)$
题外话:
$我觉得点积叉积还是写函数比较好,不重载运算符比较好$
$避免更多的括号,省得出事,而且好看,算是更新了一下板子$
代码:
//
// Created by TaoSama on 2017-04-10
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cerr << #x << " = " << x << " "
#define prln(x) cerr << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long Type;
struct Point {
Type x, y;
Point() {}
Point(Type x, Type y) : x(x), y(y) {}
void read() {scanf("%lld%lld", &x, &y);}
void write() {printf("%lld %lld\n", x, y);}
Point operator+(const Point& p) const {
return Point(x + p.x, y + p.y);
}
Point operator-(const Point& p) const {
return Point(x - p.x, y - p.y);
}
bool operator<(const Point& p) const {
return x != p.x ? x < p.x : y < p.y;
}
};
Type dot(const Point& A, const Point& B) {
return A.x * B.x + A.y * B.y;
}
Type det(const Point& A, const Point& B) {
return A.x * B.y - A.y * B.x;
}
//输入不能有重点,函数执行完后输入顺序被破坏
Point ps[N], ch[N];
int convexHull(Point* p, int n, Point* ch) {
sort(p, p + n);
int m = 0;
for(int i = 0; i < n; ++i) {
while(m > 1 && det(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) --m;
ch[m++] = p[i];
}
for(int i = n - 2, t = m; ~i; --i) {
while(m > t && det(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) --m;
ch[m++] = p[i];
}
if(n > 1) --m;
return m;
}
vector<int> rotatingCalipers(Point* ch, int n) {
if(n < 3) return vector<int>();
Type ans = 0;
vector<int> ret(3);
ch[n] = ch[0];
for(int i = 0; i < n; ++i) {
for(int j = i + 1, k = j; j < n; ++j) {
while(det(ch[j] - ch[i], ch[k + 1] - ch[i])
> det(ch[j] - ch[i], ch[k] - ch[i]))
k = (k + 1) % n;
if(det(ch[j] - ch[i], ch[k] - ch[i]) > ans) {
ans = det(ch[j] - ch[i], ch[k] - ch[i]);
ret = {i, j, k};
}
}
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int n; long long s;
scanf("%d%lld", &n, &s);
for(int i = 0; i < n; ++i) ps[i].read();
int m = convexHull(ps, n, ch);
vector<int> triangle = rotatingCalipers(ch, m);
for(int i = 0; i < 3; ++i) {
Point p = ch[triangle[i]] + ch[triangle[(i + 1) % 3]] - ch[triangle[(i + 2) % 3]];
p.write();
}
return 0;
}